package AnswerOfComent;

import structure.ListNode;

import java.util.Arrays;

/**
 * 排序链表
 * 给出链表头节点，将其按照升序排列并返回排序后的结果
 */
public class Tencent_148_sortList {
    /**
     * 大神题解，使用归并排序（递归法）
     * @param head
     * @return
     */
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 找出链表的中间节点
        // 节点数是单数，找到中间节点是一个
        // 节点数是双数，找打中间节点是两个的左边那个
        ListNode fast = head.next;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        // 先使用一个变量记录右边部分的开始位置
        ListNode temp = slow.next;
        slow.next = null;
        // 开始分割
        ListNode left = sortList(head);
        ListNode right = sortList(temp);
        // 开始合并
        ListNode h = new ListNode(0);
        ListNode res = h;
        while(left != null && right != null) {
            if (left.val > right.val) {
                h.next = right;
                right = right.next;
            } else {
                h.next = left;
                left = left.next;
            }
            h = h.next;
        }
        h.next = left == null ? right : left;
        return res.next;
    }

    /**
     * 官方题解
     */
    class Solution {
        public ListNode sortList(ListNode head) {
            return sortList(head, null);
        }

        public ListNode sortList(ListNode head, ListNode tail) {
            if (head == null) {
                return head;
            }
            if (head.next == tail) {
                head.next = null;
                return head;
            }
            // 找出链表的中间节点，这种方式合适在链表排序中使用
            ListNode slow = head, fast = head;
            while (fast != tail) {
                slow = slow.next;
                fast = fast.next;
                if (fast != tail) {
                    fast = fast.next;
                }
            }
            // 开始分割
            ListNode mid = slow;
            ListNode list1 = sortList(head, mid);
            ListNode list2 = sortList(mid, tail);
            ListNode sorted = merge(list1, list2);
            return sorted;
        }

        public ListNode merge(ListNode head1, ListNode head2) {
            ListNode dummyHead = new ListNode(0);
            ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
            while (temp1 != null && temp2 != null) {
                if (temp1.val <= temp2.val) {
                    temp.next = temp1;
                    temp1 = temp1.next;
                } else {
                    temp.next = temp2;
                    temp2 = temp2.next;
                }
                temp = temp.next;
            }
            if (temp1 != null) {
                temp.next = temp1;
            } else if (temp2 != null) {
                temp.next = temp2;
            }
            return dummyHead.next;
        }
    }
}
